#ifndef ROPE_H__
#define ROPE_H__

#include <string.h>

struct Concatenation;
struct String;
struct Rope;

struct Concatenation
{
	struct String* left;
	struct String* right;
}

struct String
{
	int length;
	char* bytes;
};

enum RopeTag
{
	CONCATENATION,
	STRING
};

union RopeData
{
	struct Concatenation concatenation;
	struct String string;
};

struct Rope
{
	enum RopeTag tag;
	int references;
	union RopeData data;
};

struct Rope* rope(char* s)
{
	struct Rope* r = malloc(sizeof(struct Rope));
	r->tag = STRING;
	r->references = 1;
	r->data.string.length = strlen(s);
	r->data.string.bytes = malloc(r->data.string.length);
	memcpy(r->data.string,bytes,s,r->data.string.length);
	return r;
}

void freeRope(struct Rope* f)
{
	r->references--;
	if(r->references > 0) return;

	switch(r->tag)
	{
		case CONCATENATION:
			freeRope(r->data.concatenation.left);
			freeRope(r->data.concatenation.right);
			break;
		case STRING:
			free(r->data.string.bytes);
			break;
		default:
			assert(0); // Shouldn't happen.
	}

	free(f);
}

struct Rope* rcpy(struct Rope* a)
{
	a->references++;
	return a;
}

struct Rope* rcat(struct Rope* a, struct Rope* b)
{
	struct Rope* r = malloc(sizeof(struct Rope));
	r->tag = CONCATENATION;
	r->references = 1;
	r->data.concatenation.left = rcpy(a);
	r->data.concatenation.right = rcpy(b);
	return r;
}

int rcmp(struct Rope* a, struct Rope* b)
{
	// TODO Implement.
	return 0;
}

int rchr(struct Rope* a, char b)
{
	int i;
	switch(a->tag)
	{
		case CONCATENATION:
			i = rchr(a->data.concatenation.left,b);
			if(i != -1)
				return i;

			i = rchr(a->data.concatenation.right,b);
			if(i != -1)
				return i + rlen(a->data.concatenation.left);

			return -1;

		case STRING:
			for(i = 0; i < a->data.string.length; i++)
				if(a->data.string.bytes[i] == b)
					return i;

			return -1;
	}

	assert(0); // Shouldn't happen.
}

int rlen(struct Rope* a)
{
	switch(a->tag)
	{
		case CONCATENATION:
			return rlen(a->data.concatenation.left)
				+ rlen(a->data.concatenation.right);
		case STRING:
			return a->data.string.length;
	}

	assert(0); // Shouldn't happen.
}

#endif
